/**
  * RSA Demo
  * 原理：
  * P、Q是两个不同的质数，令T = (P - 1) * (Q - 1)。
  * 另有正整数D、E，且D和T互质，D * E % T = 1。
  * 对正整数A且A < PQ，则
  * C = A^E % (PQ)
  * B = C^D % (PQ)
  * A = B
  * 也就是说，对原文A使用E、P、Q加密得到C，再使用D、P、Q对C进行解密得到的B，就是原文A
  */

#include<iostream>
#include<cstring>
#include<cstdint>
using namespace std;

/** calc a ^b % c,反复平方法 */
int pow_mod(int a, int b, int c)
{
	int64_t res = 1;
	int64_t tempa = a;

	while (b != 0)
	{
		if (0 != (b & 1))
		{
			res = (res * tempa) % c;
		}

		tempa = (tempa * tempa) % c;

		b >>= 1;
	}

	return static_cast<int>(res);
}

int gcd(int a, int b)
{
	int c = b;
	while (0 != c)
	{
		c = a % b;
		a = b;
		b = c;
	}

	return a;
}

int main(void)
{
	wchar_t str[] = L"Hello, world!\n";

	wcout << L"The original string: " << str;

	//step1，选择两个素数P和Q
	int P = 73, Q = 211;

	int N = P * Q;
	int T = (P - 1) * (Q - 1);

	//step2，选择整数E，使E和T互质
	int E = T / 4;
	for (; ; E--)
	{
		if (gcd(E, T) == 1)
		{
			break;
		}
	}

	//step3，选择整数D，使D * E % T = 1
	int D = 0;
	for (D = E + 1; ; D++)
	{
		if (D * E % T == 1)
		{
			break;
		}
	}

	wchar_t *p = str;
	for (; *p != '\0'; p++)
	{
		*p = pow_mod(*p, E, N);
	}

	wcout << "Entrypied characters are: ";
	//注意：在linux里不能混用cout和wcout。如果这里使用了cout，那么将不会有输出
	for (p = str; *p != L'\0'; p++)
	{
		wcout << (int)*p << " ";
	}
	wcout << endl;
	
	for (p = str; *p != L'\0'; p++)
	{
		*p = pow_mod(*p, D, N);
	}
	wcout << L"Deentrypied string is: " << str;

	return 0;
}
